#include <stdio.h>
void insert_sort(int A[], int n);
int main(void)
{
	int arr[10]={34,18,27,9,66,500,432,777,666,432};
	int i=0;
	int b;
	scanf("%d",&b);
	printf("[");
	for(;i<sizeof(arr)/4;i++)
	{
		printf("%d,",arr[i]);
	}
	printf("\b]\n");
	insert_sort(arr,b);
	printf("[");
	for(i=0;i<sizeof(arr)/4;i++)
	{
		printf("%d,",arr[i]);
	}
	printf("\b]\n");
	return 0;

}



void insert_sort(int A[], int n)
{
	int    a,i,j;
         for(i=1; i<n; i++) { //29
                 a = A[i];       //30
                 j = i-1;	//31
                 while(j>=0 && A[j]>a) {/* 非递增*/ //32
                      A[j+1] = A[j];  //33
                      j--; //34
                 } 
                 A[j+1] = a;   //36

/*

gdb
29: n=14
30: a = A[1]=18;
31: j(0) = i(1) - 1; 
32:true  ,  A[j]=34  -- A[j]代表数组的上一个元素
,这句话的意思是 如果j不为负，(j应该是一个走的指针)并且签名的比后面的大，那么就将后面的直接覆盖为前面的。
因为后面的也就是A[j+1]或A[i]已经被a保存，所以无所谓。
33:A[1](18)=A[0](34)
34: { A[0] = A[1] = 34}
j(-1)
36: A[j+1](A[0])=a(18)=18=A[0]
~~~后面和前面互换~~~
31:j(-1)=i(1)-1=0
29:i(2)<n(14)
30:a(18) = A[2] = 27
这一步又把下一个元素也就是从A[1]开始比较之后的A[2]暂存到a里面
31:j(-1)=i(2)-1=1   /~~ j是多少我don't care,它就永远用来访问数组上一个元素
32:j(1)>=0 true
这里设置这个条件的作用我觉得是为了防止用户输入i为0,
如果那样，就不会进行循环，也就不会排序，那么数组很有可能越界。
如果i=0,那么A[0]=a=A[1]也就是第一个元素将变成第二个元素，
所以不符合要求。
但是i不是输入,i只会永远增大,有i在,永远可以访问到数组。
所以i和j的作用就是,i负责便利数组，j负责对i的前一个数操作.
~~~
分析到这里发现，n并不会决定内层循环，内层循环也不一定执行，
j--不知道啥意思;
A[j](A[1])=34 > a(27) true
33: A[2]= 34
34:j(0)
~~~~~~~~~
-------
30:i = 4
A[i]=66
~ 
36:
a(66)
A[j+1](A[3+1])=66
从这一步可以看出，如果前面的比后面的大，那么后面的元素将先被替换，他的备份a则会赋值给前面的元素。
如果前面的元素没有后面的大或者和后面相等，那么36行就是后面的元素做了个备份，然后又赋给了后面的元素。
所以这个算法和输入参数是有关系的。
输入的参数不一定一定为n，在这里它变成了A[]
进一步说，就是如果arr全都是前面的小于后面的，
其实这是一个冒泡排序，
最外层负责比较n-1次,其实就是1个元素和数组中的其他元素比较
内层的则负责：
第一次：arr[1]和arr[0]比
第二次：arr[2]和arr[1]比，arr[1]和arr[0]比，过程中如果后者小于前者，
则索引对应的值立马改变.等到稳定以后，不会出现像:
[4,2,1,3]原始
[2,4,1,3]
[2,1,4,3]
[2,1,3,4]
这样的排序
相反，他会:
[4,2,1,3,3]原始 (->代表的是while循环到第36行的改变,~代表while多次循环)
1th : [4,4,1,3,3] -> [2,4,1,3,3]
2th : [2,4,4,3,3] ~ [2,2,4,3,3] -> [1,2,4,3,3]
~~~
4th : 没有任何动作 -> A[4]=a
举个最坏的情况的例子:
[7,6,5,4,3]原始
[7,7,5,4,3]->[6,7,5,4,3]
[6,7,7,4,3]~[6,6,7,4,3]->[5,6,7,4,3]
[5,6,7,7,3]~[5,6,6,7,3]~[5,5,6,7,3]->[4,5,6,7,3]
[4,5,6,7,7]~[4,5,6,6,7]~[4,5,5,6,7]~[4,4,5,6,7]->[3,4,5,6,7]
再举个最好的例子:
~~这里的n为数组.size()~~
[3,4,5,6,7]原始
none->[3,4,5,6,7]
none->[3,4,5,6,7]
none->[3,4,5,6,7]
none->[3,4,5,6,7]
~~~
如果n=0|1,那么循环将不会开始。也就失去了算法的意义。


如果n=2,3,...,数组.size(),那么，外层循环将为(n-1)
	如果数组为全顺阶，那么内层循环将为1*(n-1)。O(n)=n
        如果数组为全逆阶，那么内层循环将为0+1+2+...+(n-2)=(n-2)(n-1)*0.5 O(n)=n^2

这个算法叫插入排序算法，如果n=数组.size()就是冒泡排序了。
不同的是这个算法可以自定义排序的个数。





*/






}
} 
